package labuladong.动态规划;

public class 正则表达式匹配 {
    public static void main(String[] args) {
        System.out.println(isMathc("ab", "a*"));
    }

    public static boolean isMathc(String text, String pattern) {
        int len1 = text.length();
        int len2 = pattern.length();
        boolean dp[][] = new boolean[len1+1][len2+1];
        return digui(text, pattern, 0, 0, dp);
    }

    public static boolean digui(String text, String pattern, int i, int j, boolean[][] dp) {
        if (j == pattern.length()-1)  {
            return i == text.length() - 1;
        }
        boolean first = i < text.length() && (pattern.charAt(j)==text.charAt(i) || pattern.charAt(j)=='.');
        if (j < pattern.length()-2 && pattern.charAt(j+1) == '*') {
            dp[i+1][j+1] = (first&&digui(text, pattern, i, j+2, dp)) || (first && digui(text, pattern, i+1, j, dp));
        } else {
            dp[i+1][j+1] = first && digui(text, pattern, i+1, j+1, dp);
        }
        return dp[i+1][j+1];
    }
}
